package seqlist.leetcode;

public class Num21 {
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        // 边界
//        if (list1 == null) {
//            return list2;
//        }
//        if (list2 == null) {
//            return list1;
//        }
//        // 此时l1和l2都不为空
//        ListNode dummyHead = new ListNode(101);
//        ListNode last = dummyHead;
//        while (list1 != null && list2 != null) {
//            if (list1.val <= list2.val) {
//                last.next = list1;
//                last = list1;
//                list1 = list1.next;
//            }else {
//                last.next = list2;
//                last = list2;
//                list2 = list2.next;
//            }
//        }
//        // 此时l1或l2为空
//        if (list1 == null) {
//            last.next = list2;
//        }else {
//            last.next = list1;
//        }
//        return dummyHead.next;
//    }
    // 递归法
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val <= list2.val) {
            // 说明此时要把list1.next和整个list2交给merge
            // 然后将结果拼接到list1.next
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}
